package com.datastructure.test.findtargetsumways;

public class FindTargetSumWays {

    public static void main(String[] args) {

    }

    static int count = 0;
    public int findTargetSumWays (int[] nums, int target) {
        // write code here
        //特殊情况
        if(nums.length == 0)
            return 0;
        // dfs回溯
        dfs(nums,target,0,0);
        return count;
    }
    public void dfs(int[] nums, int target, int index, int sum){
        // 走到最后一个索引位置
        if(index == nums.length){
            // sum和等于target 就加一
            if(sum == target)
                count++;
        }
        else{
            // dfs回溯 +操作
            dfs(nums,target,index+1,sum + nums[index]);
            // dfs回溯 -操作
            dfs(nums,target,index+1,sum -nums[index]);
        }
    }

    public int findTargetSumWays1 (int[] nums, int target) {
        if(nums.length == 0) return 0;
        int sum = 0, index = 0;
        for(int num : nums) sum += num;
        if((target+sum)%2 != 0) return 0;
        index = (target+sum)/2;
        int[] dp = new int[index+1];
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++) {
            for(int j = index; nums[i] <= j; j--) {
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[index];
    }

}
